//
//  冒泡排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/1.
//  时间复杂度n^2，原地稳定排序

import Foundation

/// 冒泡排序(从小到大)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func bubbleSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    for (i, _) in a.enumerated() {
        for j in 0..<(a.count - i - 1) {
            if a[j] > a[j + 1] {
                let temp = a[j]
                a[j] = a[j + 1]
                a[j + 1] = temp
            }
        }
    }
    return a
}

/// 冒泡排序(从小到大)
/// 优化1：外层循环剩下的可能是已经排好序的，加个标志位，只要内层循环没有交换过，就退出整个循环
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func bubbleSortOptimization1(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    for (i, _) in a.enumerated() {
        // 数据交换标记位
        var flag = false
        for j in 0..<(a.count - i - 1) {
            if a[j] > a[j + 1] {
                let temp = a[j]
                a[j] = a[j + 1]
                a[j + 1] = temp
                flag = true
            }
        }
        // 没有数据交换退出
        if !flag { break }
    }
    return a
}

/// 冒泡排序(从小到大)
/// 优化2：在冒泡排序中还有一个问题存在，就是第 i 趟排的第 i 小或者大的元素已经在第 i 位上了，甚至可能第 i-1 位也已经归位了，那么在内层循环的时候，有这种情况出现就会导致多余的比较出现。例如：6，4，7，5，1，3，2，当我们进行第一次排序的时候，结果为6，7，5，4，3，2，1，实际上后面有很多次交换比较都是多余的，因为没有产生交换操作。利用一个标志位，记录一下当前第 i 趟所交换的最后一个位置的下标，在进行第 i+1 趟的时候，只需要内循环到这个下标的位置就可以了，因为后面位置上的元素在上一趟中没有换位，这一次也不可能会换位置了。
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func bubbleSortOptimization2(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    var len = a.count - 1
    var tempPostion = 0 // 记录最后一次交换的位置
    for _ in a {
        // 数据交换标记位
        var flag = false
        for j in 0..<len {
            if a[j] > a[j + 1] {
                let temp = a[j]
                a[j] = a[j + 1]
                a[j + 1] = temp
                flag = true
                //记录交换的位置
                tempPostion = j
            }
        }
        //把最后一次交换的位置给len，来缩减内循环的次数
        len = tempPostion
        // 没有数据交换退出
        if !flag { break }
    }
    return a
}

